package hash;

import org.junit.Test;

import java.util.*;

//给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表
public class LeetCode_49 {

    public List<List<String>> groupAnagrams(String[] strs) {
        return solution_1(strs);
    }


    @Test
    public void test_solution1(){
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> lists = solution_1(strs);
        for (List<String> list : lists) {
            for (String s : list) {
                System.out.print(s+" ");
            }
            System.out.println();
        }
    }

    @Test
    public void test_solution2(){
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> lists = solution_2(strs);
        for (List<String> list : lists) {
            for (String s : list) {
                System.out.print(s+" ");
            }
            System.out.println();
        }
    }

    private static class MySet{
        HashMap<Character,Integer> set=new HashMap<>();

        //单词加入
        public MySet(String str){
            //1. 逐个判断字符
            for (int i = 0; i < str.length(); i++) {
                //1.1 字符在哈希表中
                if (set.containsKey(str.charAt(i))){
                    set.put(str.charAt(i),set.get(str.charAt(i))+1);
                }else{      //1.2 字符不在哈希表中
                    set.put(str.charAt(i),0);
                }
            }
        }

        //判断set是否相同
        public Boolean isSame(MySet mySet){
            Map set1 = mySet.set;
            //1. 判断个数相同
            if (set1.size()!=set.size()){
                return false;
            }
            //2. 逐元素判断是否相同
            for (Character c : set.keySet()) {
                //2.1 判断count是否相同
                if (set.get(c)!=set1.get(c)){
                    return false;
                }
            }
            return true;
        }

    }


    /**
     * 方法1：使用自定义set存储str的每个字符出现次数，通过这个判断str是否相同
     * @param strs
     * @return
     */
    public static List<List<String>> solution_1(String[] strs){
        //1. 定义返回值，以及当前的index
        List<List<String>> results = new ArrayList<>();
        ArrayList<MySet> results_set = new ArrayList<>();

        //2. 逐个判断strs
        for (String str : strs) {
            //2.1 判断str的set和之前的set是否相同
            MySet currentSet = new MySet(str);
            int tempIndex = isInResults(results_set,currentSet);

            //2.2 之前存在过
            if (tempIndex>=0){
                results.get(tempIndex).add(str);
            }else {     //2.3 之前不存在过
                ArrayList<String> list = new ArrayList<>();
                list.add(str);
                results.add(list);
                results_set.add(currentSet);
            }

        }
        //3. 返回结果
        return results;


    }

    //判断之前的results_set是否存在set函数
    public static Integer isInResults(ArrayList<MySet> sets,MySet set){
        //1. 逐个判断sets
        for (int i = 0; i < sets.size(); i++) {
            if (set.isSame(sets.get(i))){
                return i;
            }
        }
        return -1;
    }

    /**
    * @Description: 方法2：使用str排序之后的str作为key
    * @Author: kunkun
    * @Date:  2025/2/27 15:39
    * @Parameters:
    * @Return
    * @Throws
    */
    public static List<List<String>> solution_2(String[] strs){

        //1. 定义返回结果
        List<List<String>> results = new ArrayList<>();
        Map<String,List<String>> results_map = new HashMap<>();

        //2. 遍历strs
        for (String str : strs) {
            //2.1 获得排序之后的str
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String sortStr = new String(chars);

            //2.2 判断map中是否包含sortStr，包含则加入，否则新增
            if (results_map.containsKey(sortStr)){
                List<String> list = results_map.get(sortStr);
                list.add(str);
                results_map.put(sortStr,list);
            }else {
                ArrayList<String> list = new ArrayList<>();
                list.add(str);
                results_map.put(sortStr,list);
            }
        }
        //3. 遍历map中所有的values
        for (List<String> list : results_map.values()) {
            results.add(list);
        }
        return results;

    }








}
